# coding=utf-8
# Date: 2021/8/24 10:03
from typing import List


# 执行用时：176 ms, 在所有 Python3 提交中击败了60.71%的用户
# 内存消耗：15.4 MB, 在所有 Python3 提交中击败了83.33%的用户
class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        N, INF = 110, 0x3f3f3f3f
        dist = [INF] * N
        dist[src] = 0
        for i in range(k + 1):
            backup = dist.copy()
            for edge in flights:
                a, b, w = edge[0], edge[1], edge[2]
                dist[b] = min(dist[b], backup[a] + w)
        if dist[dst] > INF / 2:
            return -1
        return dist[dst]


if __name__ == "__main__":
    flight = [[0, 1, 100], [1, 2, 100], [0, 2, 500]]
    print(Solution().findCheapestPrice(3, flight, 0, 2, 1))  # 200
